package 力扣._5_最长回文数组;

public class Solution {
    public String longestPalindrome(String s) {
        //从各个点向两侧扩散，奇数个、偶数个
        int[] ji = new int[s.length()];  //ji[i],下标i为中点的回文串
        int[] ou = new int[s.length()];  //ou[i],下标i,i+1为中点的回文串

        //奇数
        int max_ji = 0;
        for (int i = 0; i < s.length(); i++) {
            int l = i - 1, r = i + 1;
            ji[i] = 1;
            while (l >= 0 && r < s.length()) {
                if (s.charAt(l) == s.charAt(r))
                    ji[i] += 2;
                else
                    break;
                l--;
                r++;
            }
            if (ji[max_ji] < ji[i])
                max_ji = i;
        }
        //偶数
        int max_ou = 0;
        for (int i = 0; i < s.length(); i++) {
            int l = i, r = i + 1;
            while (l >= 0 && r < s.length()) {
                if (s.charAt(l) == s.charAt(r))
                    ou[i] += 2;
                else
                    break;
                l--;
                r++;
            }
            if (ou[max_ou] < ou[i])
                max_ou = i;
        }
        if (ji[max_ji] > ou[max_ou]) {
            return s.substring(max_ji - (ji[max_ji] / 2), max_ji + ji[max_ji] / 2 + 1);
        } else {
            return s.substring(max_ou - (ou[max_ou] / 2 - 1), max_ou + ou[max_ou] / 2 + 1);
        }
    }

    public static void main(String[] args) {
        String s = new Solution().longestPalindrome("babad");
        System.out.println(s);
    }
}
